Ordre total

En matemàtiques, un ordre lineal, ordre total, ordre simple o també ordenació és una relació binària (que en aquest article denotarem mitjançant per l'infix ≤) en un conjunt X. Aquesta relació és transitiva, antisimètrica i total. Un conjunt amb un ordre total s'anomena conjunt totalment ordenat, o cadena.

Si X és totalment ordenat per ≤, llavors les següents afirmacions són certes per a, b i c de X qualssevol:

• Si a ≤ b i b ≤ a, llavors a = b (antisimetria).
• Si a ≤ b i b ≤ c, llavors a ≤ c (transitivitat).
• Es té que a ≤ b o bé b ≤ a (totalitat).

L'antisimetria elimina els casos incerts en què a precedeix b i alhora b precedeix a.^[1] Una relació amb la propietat de «totalitat» vol dir que tot parell d'elements del conjunt de la relació són comparables per la relació. Això també vol dir que el conjunt es pot simbolitzar com una línia d'elements.^[2] La totalitat també implica la reflexivitat, és a dir, a ≤ a. Per tant, un ordre total és també un ordre parcial. L'ordre parcial té una forma més feble de la tercera condició (només requereix reflexivitat, no totalitat). Una extensió d'un ordre parcial donat a un ordre total s'anomena extensió lineal de l'ordre parcial.